package com.yan_jiu_sheng.LeetCodeHot100.AC;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/coin-change/description/?envType=study-plan-v2&envId=top-100-liked
 * 参考通过
 *
 * @author yulongtian
 * @create 2024-07-22 18:34
 */
public class Test81 {
    public static void main(String[] args) {
        int[] coins = {2, 3, 5};
        int amount = 11;
        System.out.println(new Test81().coinChange(coins, amount));
    }

    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

//    /*
//    不太行，记忆化优化没成功
//     */
//    public int coinChange(int[] coins, int amount) {
//        int n = coins.length;
//        int[] memory = new int[n];
//        Arrays.fill(memory, amount + 1);
//        int res = dfs(n - 1, coins, amount, amount + 1, memory);
//        return res > amount ? -1 : res;
//    }
//
//    public int dfs(int i, int[] coins, int amount, int max, int[] memory) {
//        if (i < 0) {
//            return amount == 0 ? 0 : max;
//        }
//        if (memory[i] != max) {
//            return memory[i];
//        }
//        if (amount < coins[i]) {
//            int dfs = dfs(i - 1, coins, amount, max, memory);
//            memory[i] = dfs;
//            return dfs;
//        }
//        int res = Math.min(dfs(i - 1, coins, amount, max, memory), dfs(i, coins, amount - coins[i], max, memory) + 1);
//        memory[i] = res;
//        return res;
//    }
}
